﻿namespace Leetcode.N2097;
public class Solution
{
    public int[][] ValidArrangement(int[][] pairs)
    {
        var edges = new Dictionary<int, Stack<int>>();
        var indeg = new Dictionary<int, int>();
        var outdeg = new Dictionary<int, int>();
        for (int i = 0; i < pairs.Length; i++)
        {
            var left = pairs[i][0];
            var right = pairs[i][1];
            if (!edges.ContainsKey(left))
            {
                edges.Add(left, new Stack<int>());
            }
            edges[left].Push(right);

            if (!outdeg.ContainsKey(left))
            {
                outdeg.Add(left, 0);
                indeg.Add(left, 0);
            }

            if (!outdeg.ContainsKey(right))
            {
                outdeg.Add(right, 0);
                indeg.Add(right, 0);
            }
            outdeg[left]++;
            indeg[right]++;
        }

        var start = pairs[0][0];

        foreach (var p in outdeg.Keys)
        {
            if (outdeg[p] == indeg[p] + 1)
            {
                start = p;
                break;
            }
        }

        var path = new Stack<int[]>();
        this.Dfs(edges, start, path);

        return path.ToArray();
    }

    private void Dfs(IDictionary<int, Stack<int>> edges, int left, Stack<int[]> path)
    {

        while (edges.ContainsKey(left) && edges[left].Count > 0)
        {
            var right = edges[left].Pop();
            this.Dfs(edges, right, path);
            path.Push(new int[] { left, right });
        }

    }

}